import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

import java.util.Arrays;

/**
 * 有效的字母异位词
 * 题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * <p>
 * 示例1:
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * <p>
 * 示例 2:
 * 输入: s = "rat", t = "car"
 * 输出: false
 * <p>
 * 说明:
 * 你可以假设字符串只包含小写字母。
 * <p>
 * 进阶:
 * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 *
 * 解答：
 * 使用哈希表而不是固定大小的计数器。想象一下，分配一个大的数组来适应整个 Unicode 字符范围，这个范围可能超过 100万。哈希表是一种更通用的解决方案，可以适应任何字符范围
 * <p>
 * 来源：力扣（LeetCode-242）
 * 链接：https://leetcode-cn.com/problems/valid-anagram
 *
 * @author godfrey
 * @since 2020-10-28
 */
@DisplayName("有效的字母异位词")
public class IsAnagram extends BaseTest {

    @DisplayName("排序-时间复杂度：O(nlog n),空间复杂度：O(1)")
    @ParameterizedTest
    @CsvSource({"anagram, nagaram"})
    void isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            System.out.println(false);
            return;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        System.out.println(Arrays.equals(str1, str2));
    }

    @DisplayName("哈希表-时间复杂度：O(n),空间复杂度：O(1)")
    @ParameterizedTest
    @CsvSource({"anagram, nagaram"})
    void isAnagram2(String s, String t) {
        if (s.length() != t.length()) {
            System.out.println(false);
            return;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++table[s.charAt(i) - 'a'];
        }
        for (int i = 0; i < t.length(); ++i) {
            if (--table[t.charAt(i) - 'a'] < 0) {
                System.out.println(false);
                return;
            }
        }
        System.out.println(true);
    }
}
